๐Ÿงฉ Deadlock

@Seongukbaek Posted August 11, 2022 ยท Updated August 11, 2022 ยท 9 min read

๐Ÿงท Deadlock

๋ฐ๋“œ๋ฝ์ด๋ž€, ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž์›์„ ์–ป์ง€ ๋ชปํ•ด ๋‹ค์Œ ์ฒ˜๋ฆฌ๋ฅผ ํ•˜์ง€ ๋ชปํ•˜๋Š” ์ƒํƒœ๋กœ, "๊ต์ฐฉ ์ƒํƒœ" ๋ผ๊ณ ๋„ ํ•˜๋ฉฐ ์‹œ์Šคํ…œ์ ์œผ๋กœ ํ•œ์ •๋œ ์ž์›์„ ์—ฌ๋Ÿฌ ๊ณณ์—์„œ ์‚ฌ์šฉํ•˜๋ ค ํ•  ๋•Œ ๋ฐœ์ƒํ•œ๋‹ค.

  • ์‹œ์Šคํ…œ์€ ์œ ํ•œํ•œ ์ž์›์„ ๊ฐ€์ง„๋‹ค. (CPU cycles, Files, I/O devices, locks) ๊ทธ๋ฆฌ๊ณ  ๊ทธ๋ ‡๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์ด๋‹ค.
  • Deadlocked๋Š” ๋ชจ๋“  ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค์— ์˜ํ•ด ๋ฐœ์ƒ๋  ์ˆ˜ ์žˆ๋Š” ์ด๋ฒคํŠธ๋ฅผ ๊ธฐ๋‹ค๋ฆฌ๊ณ  ์žˆ๋Š” ์ƒํƒœ๋ผ๊ณ ๋„ ํ•  ์ˆ˜ ์žˆ๋‹ค.

๐Ÿชš ๋ฐœ์ƒ ์กฐ๊ฑด

๋ฐ๋“œ๋ฝ์€ ์–ธ์ œ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ์„๊นŒ? ์•„๋ž˜์˜ ๋„ค ๊ฐ€์ง€ ์กฐ๊ฑด์ด ๋™์‹œ์— ์„ฑ๋ฆฝํ•  ๋•Œ ๋ฐœ์ƒํ•œ๋‹ค. ํ•˜๋‚˜๋ผ๋„ ์„ฑ๋ฆฝํ•˜์ง€ ์•Š๋„๋ก ํ•˜๋ฉด, ๊ต์ฐฉ ์ƒํƒœ๋ฅผ ํ”ผํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์ด๋‹ค.

์ƒํ˜ธ ๋ฐฐ์ œ(Mutual Exclusion)

  • ์ž์›์€ ํ•œ ๋ฒˆ์— ํ•œ ํ”„๋กœ์„ธ์Šค๋งŒ์ด ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•œ๋‹ค. ์ ์–ด๋„ ํ•˜๋‚˜์˜ ์ž์›์€ ๊ณต์œ ๋˜์ง€ ์•Š์•„์•ผ ํ•œ๋‹ค.

์ ์œ  ๋Œ€๊ธฐ(Hold and Wait)

  • ์ ์–ด๋„ ํ•˜๋‚˜์˜ ์ž์›์„ ํ• ๋‹นํ•˜๊ณ  ์žˆ์–ด์•ผ ํ•˜๊ณ , ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค๋“ค์— ์žกํ˜€์žˆ๋Š” ์ž์›์„ ์ ์œ ํ•˜๊ธฐ ์œ„ํ•ด ๋Œ€๊ธฐํ•˜๋Š” ํ”„๋กœ์„ธ์Šค๊ฐ€ ์žˆ์–ด์•ผ ํ•œ๋‹ค.

๋น„์„ ์ (No Preemption)

  • ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค์— ํ• ๋‹น๋œ ์ž์›์€ ์‚ฌ์šฉ์ด ๋๋‚  ๋•Œ๊นŒ์ง€ ๊ฐ•์ œ๋กœ ์„ ์ ํ•  ์ˆ˜ ์—†์–ด์•ผ ํ•œ๋‹ค.

์ˆœํ™˜ ๋Œ€๊ธฐ(Circular Wait)

  • ํ”„๋กœ์„ธ์Šค ์ง‘ํ•ฉ์—์„œ P0์€ P1์ด ์ ์œ ํ•œ ์ž์›์„ ๋Œ€๊ธฐํ•˜๊ณ , P1์€ P2๊ฐ€ ์ ์œ ํ•œ ์ž์›์„ ๋Œ€๊ธฐ, ์ด๊ฐ€ ๋ฐ˜๋ณต๋˜์–ด Circle์„ ์ƒ์„ฑํ•œ๋‹ค.
  • ์ด๋Š” ์ ์œ  ๋Œ€๊ธฐ๋กœ ์ธํ•ด ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋‹ค.

์ž์› ํ• ๋‹น ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ ค๋ณด์•˜์„ ๋•Œ, ์‚ฌ์ดํด์ด ์ƒ์„ฑ๋œ๋‹ค๋ฉด ๋ฐ๋“œ๋ฝ์ด ์กด์žฌํ•  ์ˆ˜๋„ ์žˆ๋‹ค. ์ด๋Š” ๊ทธ์ € ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ์Œ์„ ์˜๋ฏธํ•˜๊ธฐ์— ๋ฐ๋“œ๋ฝ์ด ์กด์žฌํ•˜์ง€ ์•Š์„ ์ˆ˜๋„ ์žˆ๋‹ค.

  • ํ•˜์ง€๋งŒ ์‚ฌ์ดํด์ด ์—†๋‹ค๋ฉด, ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š”๋‹ค๋Š” ๊ฒƒ์„ ๋ณด์žฅํ•œ๋‹ค.

๐Ÿงท Deadlock ์ฒ˜๋ฆฌ

๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ „๋žต์ด ์žˆ๋‹ค.

๋ฐ๋“œ๋ฝ์„ ๋ฐฉ์ง€ํ•˜๊ฑฐ๋‚˜ ํ”ผํ•˜๊ธฐ ์œ„ํ•œ ํ”„๋กœํ† ์ฝœ์„ ์‚ฌ์šฉ

  • ์‹œ์Šคํ…œ์ด ์ ˆ๋Œ€๋กœ ๋ฐ๋“œ๋ฝ์— ๋“ค์–ด๊ฐ€์ง€ ์•Š๋„๋ก ๋ณด์žฅํ•œ๋‹ค.
  • Deadlock prevention๊ณผ Deadlock avoidance๊ฐ€ ์žˆ๋‹ค.

    • avoidance๋ฅผ ์œ„ํ•ด์„œ๋Š” ์ถ”๊ฐ€์ ์ธ ์ •๋ณด๊ฐ€ ํ•„์š”ํ•˜๋‹ค.

์‹œ์Šคํ…œ์ด ๋ฐ๋“œ๋ฝ์— ๋“ค์–ด๊ฐ€๋Š” ๊ฒƒ์„ ํ—ˆ์šฉํ•˜๋˜, ์ด๋ฅผ ๊ฐ์ง€ํ•˜๊ณ  ๋ณต๊ตฌ

๋ฐ๋“œ๋ฝ์˜ ๋ฐœ์ƒ์„ ์™œ ์ฒ˜๋ฆฌํ•˜์ง€ ์•Š๋Š”๊ฐ€? ๋Œ€๋ถ€๋ถ„์˜ ์‹œ์Šคํ…œ์€ ๋ฐ๋“œ๋ฝ์ด ์ž˜ ๋ฐœ์ƒํ•˜์ง€ ์•Š์œผ๋ฉฐ, ๋ฐ๋“œ๋ฝ ์˜ˆ๋ฐฉ, ํšŒํ”ผ, ํƒ์ง€ ๋ฐ ๋ณต๊ตฌํ•˜๋Š” ๊ฒƒ์€ ๋น„์šฉ์ด ๋งŽ์ด ๋“ ๋‹ค.

๋ฐ๋“œ๋ฝ ๋ฌด์‹œ

  • ๊ฐ€์žฅ ๋งŽ์ด ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•

๐Ÿชš Deadlock Prevention

๋ฐ๋“œ๋ฝ์€ ๋ฐœ์ƒ ์กฐ๊ฑด 4๊ฐ€์ง€๊ฐ€ ๋ชจ๋‘ ์„ฑ๋ฆฝ๋˜์–ด์•ผ ๋ฐœ์ƒํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ํ•œ ๊ฐ€์ง€ ์กฐ๊ฑด๋งŒ ์„ฑ๋ฆฝ๋˜์ง€ ์•Š๋”๋ผ๋„ ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š”๋‹ค. ๋ฐ๋“œ๋ฝ ์˜ˆ๋ฐฉ์€ ์ ์–ด๋„ ํ•œ ๊ฐ€์ง€ ์กฐ๊ฑด์ด ์„ฑ๋ฆฝํ•˜์ง€ ์•Š๋Š”๋‹ค๊ณ  ๋ณด์žฅํ•œ๋‹ค.

  • ๊ฐ 4๊ฐ€์ง€ ์กฐ๊ฑด์— ๋Œ€ํ•œ ๋ถ€์ •์„ ํ†ตํ•ด ๋ฐ๋“œ๋ฝ์„ ์˜ˆ๋ฐฉํ•˜๋„๋ก ํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

Mutual Exclusion - ์ƒํ˜ธ ๋ฐฐ์ œ

  • ๋ฉ€ํ‹ฐ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž์›์„ ๊ณต์œ ํ•˜๋„๋ก ํ•˜์—ฌ ์ƒํ˜ธ ๋ฐฐ์ œ๋ฅผ ๋ถ€์ •ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ์ž์›์„ ๊ณต์œ ๊ฐ€ ๊ฐ€๋Šฅํ•˜๋„๋ก ๋งŒ๋“ ๋‹ค. (ex. read-only file : ์—ฌ๋Ÿฌ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ฝ๊ธฐ ๊ฐ€๋Šฅํ•˜๋‹ค.)
  • ํ•˜์ง€๋งŒ, ์ž์›์„ ๊ณต์œ ๊ฐ€ ๊ฐ€๋Šฅํ•˜๋„๋ก ๋งŒ๋“œ๋Š” ๊ฒƒ์ด ์–ด๋ ต๋‹ค.

Hold and Wait - ์ ์œ  ๋Œ€๊ธฐ

  • ์ƒํ˜ธ ๋ฐฐ์ œ๋ฅผ ๋ถ€์ •ํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค๋Š” ์‰ฌ์šด ๋ฐฉ๋ฒ•์œผ๋กœ, ๋‘ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค.

    • ๋ชจ๋“  ํ”„๋กœ์„ธ์Šค๊ฐ€ ์‹คํ–‰ ์ „์— ํ•„์š”ํ•œ ์ž์›์„ ๋ชจ๋‘ ์š”์ฒญํ•˜์—ฌ ํ• ๋‹น๋ฐ›๋„๋ก ํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ํ•˜์ง€๋งŒ ์ด๋Š” ๋‚ฎ์€ ์ž์› ํ™œ์šฉ๋„๊ฐ€ ๋ฌธ์ œ๊ฐ€ ๋œ๋‹ค.
    • ๋ชจ๋“  ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž์›์„ ํ•˜๋‚˜๋„ ๊ฐ€์ง€๊ณ  ์žˆ์ง€ ์•Š์€ ๊ฒฝ์šฐ์—๋งŒ ์ž์›์„ ์š”์ฒญํ•˜๋„๋ก ํ•œ๋‹ค. (์ž์›์„ ์–ป๊ณ , ์‚ฌ์šฉํ•˜๊ณ  ํ•ด์ œ, ๋˜ ์–ป๊ณ  ์‚ฌ์šฉํ•˜๊ณ  ํ•ด์ œ, ์ด๋ฅผ ๋ฐ˜๋ณต) ํ•˜์ง€๋งŒ ์ด๋Š” Starvation์ด ๋ฌธ์ œ๊ฐ€ ๋œ๋‹ค.

No Preemption - ๋น„์„ ์ 

  • ์ž์›์„ ์ ์œ ํ•˜๊ณ  ์žˆ๋Š” ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋‹ค๋ฅธ ์ž์›์„ ์š”๊ตฌํ•  ๋•Œ, ์ ์œ ํ•˜๊ณ  ์žˆ๋Š” ๋ชจ๋“  ์ž์›์„ ๋ฐ˜๋‚ฉํ•˜๊ณ , ์š”๊ตฌํ•œ ์ž์›์„ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด ๊ธฐ๋‹ค๋ฆฌ๊ฒŒ ํ•œ๋‹ค.
  • ์ž์›์ด ์„ ์  ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ์—๋งŒ ๊ฐ€๋Šฅํ•˜๋‹ค.

Circular Wait - ์ˆœํ™˜ ๋Œ€๊ธฐ

  • ๋ชจ๋“  ์ž์›์˜ ์ˆœ์„œ๋ฅผ ์ •ํ•˜๊ณ , ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ด ์ˆœ์„œ์— ๋งž๊ฒŒ ์ž์›์„ ์š”์ฒญํ•˜๋„๋ก ํ•œ๋‹ค.

๋ฐ๋“œ๋ฝ ์˜ˆ๋ฐฉ์€ ์ž์›์˜ ๋‚ญ๋น„๊ฐ€ ์‹ฌํ•˜๋‹ค๋Š” ๋‹จ์ ์ด ์žˆ๋‹ค.

๐Ÿชš Deadlock Avoidance

๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•˜๋ฉด ์ด๋ฅผ ํ”ผํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

  • ์ž์›์ด ์–ด๋–ป๊ฒŒ ์š”์ฒญ๋˜๋Š”์ง€์— ๋Œ€ํ•œ ์ถ”๊ฐ€ ์ •๋ณด๊ฐ€ ํ•„์š”ํ•˜๋‹ค.
  • ๊ฐ ์š”์ฒญ๋งˆ๋‹ค, ์š”์ฒญ์ด ๋ฐ›์•„๋“ค์—ฌ์งˆ์ง€, ๋Œ€๊ธฐํ• ์ง€๋ฅผ ๊ฒฐ์ •ํ•œ๋‹ค.
  • ์ •๋ณด์˜ ์–‘๊ณผ ์œ ํ˜•์— ๋”ฐ๋ผ ๋‹ค์–‘ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ ์šฉ๋  ์ˆ˜ ์žˆ๋‹ค.

Safe state

  • ์ด ์ƒํƒœ์—์„œ๋Š”, ์‹œ์Šคํ…œ์€ ๊ฐ ํ”„๋กœ์„ธ์Šค์— ์ž์›์„ ํ• ๋‹นํ•  ์ˆ˜ ์žˆ๊ณ , ๋ฐ๋“œ๋ฝ์„ ํ”ผํ•  ์ˆ˜ ์žˆ๋‹ค.

    • ๋ชจ๋“  ์š”์ฒญ์„ ๋งŒ์กฑํ•  ์ˆ˜ ์žˆ๋Š” Safe sequence(ํ”„๋กœ์„ธ์Šค์˜ ์ˆœ์„œ)๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ์—๋งŒ ๊ฐ€๋Šฅํ•˜๋‹ค.

Unsafe state

  • safeํ•˜์ง€ ์•Š์€ ์ƒํƒœ๋กœ, ๋ฌด์กฐ๊ฑด ๋ฐ๋“œ๋ฝ์„ ์˜๋ฏธํ•˜๋Š” ๊ฒƒ์€ ์•„๋‹ˆ๋‹ค.
  • ํ•˜์ง€๋งŒ ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋Š” ์ƒํƒœ์ด๋‹ค.

Resource-Allocation-Graph ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ์ž์› ํ• ๋‹น ๊ทธ๋ž˜ํ”„๊ฐ€ ์‚ฌ์ดํด์„ ์ƒ์„ฑํ•˜๋Š” ์—ฌ๋ถ€๋ฅผ ํŒŒ์•…ํ•ด์•ผ ํ•œ๋‹ค.
  • ํ•ด๋‹น ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์œ„ํ•ด์„œ๋Š” Claim edge์™€ Request edge๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.

    • Claim edge๋Š” ํŠน์ • ํ”„๋กœ์„ธ์Šค๊ฐ€ ํŠน์ • ์ž์›์„ ๋ฏธ๋ž˜์— ์š”์ฒญํ•  ๊ฒƒ์ž„์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.
    • Request edge๋Š” ํŠน์ • ํ”„๋กœ์„ธ์Šค๊ฐ€ ํŠน์ • ์ž์›์„ ์š”์ฒญํ•จ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.
  • Claim edge๋Š” ์‹ค์ œ๋กœ ํ•ด๋‹น ์š”์ฒญ์ด ๋ฐœ์ƒํ–ˆ์„ ๋•Œ Request edge๋กœ ๋ณ€๊ฒฝ๋œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํ•ด๋‹น ์ž์›์„ ํ•ด์ œํ•˜๋ฉด ๋‹ค์‹œ Claim edge๋กœ ๋ณ€๊ฒฝ๋œ๋‹ค.
  • ํ•ด๋‹น edge๋“ค์ด ์‚ฌ์ดํด์„ ํ˜•์„ฑํ•œ๋‹ค๋ฉด ์ž์›์˜ ํ• ๋‹น์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๋„๋ก ํ•œ๋‹ค.

Banker's ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • Resource-Allocation-Graph ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ multi-resource ๋ฌธ์ œ์—์„œ ์ ์šฉ ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค.

    • ์‚ฌ์ดํด์ด ์กด์žฌํ•˜๋”๋ผ๋„, multiple instance๋ฅผ ๊ฐ€์ง„๋‹ค๋ฉด ๋ฐ๋“œ๋ฝ์ด ๋ฌด์กฐ๊ฑด ๋ฐœ์ƒํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
  • Banker's ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ฐ๋“œ๋ฝ ๋ฐฉ์ง€๋ฅผ ์œ„ํ•ด ํ• ๋‹น ์ˆœ์„œ๋ฅผ ํ™•์ธํ•œ๋‹ค.

    • ์ƒˆ๋กœ์šด ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋“ค์–ด์˜ค๋ฉด, ๊ฐ ์ž์› ์œ ํ˜•์˜ ์ธ์Šคํ„ด์Šค์˜ ์ตœ๋Œ€ ์ˆ˜๋ฅผ ๋ช…์‹œํ•ด์•ผ ํ•œ๋‹ค.
    • ์š”์ฒญ ์ƒ์„ฑ ์‹œ, ์š”์ฒญ๋œ ํ• ๋‹น์„ safe state์— ์žˆ๋Š” ์‹œ์Šคํ…œ์— ํ• ๋‹นํ• ์ง€ ๋Œ€๊ธฐ์‹œํ‚ฌ์ง€ ๊ฒฐ์ •ํ•œ๋‹ค.
  • ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž์›์„ ์š”๊ตฌํ•  ๋•Œ ์‹œ์Šคํ…œ์€ ์ž์›์„ ํ• ๋‹นํ•œ ํ›„์—๋„ Safe state๋กœ ๋‚จ์•„์žˆ๊ฒŒ ๋˜๋Š”์ง€๋ฅผ ์‚ฌ์ „์— ๊ฒ€์‚ฌํ•˜์—ฌ ๋ฐ๋“œ๋ฝ์„ ํšŒํ”ผํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

    • ๊ฒ€์‚ฌํ•˜์—ฌ Safe state์— ์žˆ๋‹ค๋ฉด ์ž์›์„ ํ• ๋‹นํ•˜๊ณ , ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค๋“ค์ด ์ž์›์„ ํ•ด์ œํ•  ๋•Œ๊นŒ์ง€ ๋Œ€๊ธฐํ•œ๋‹ค.

๐Ÿ“• ์ฐธ๊ณ 

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€